package com.sjf.day02.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        System.out.println("测试单链表---》");
        HeroNode node  = new HeroNode(1, "aa", "AA");
        HeroNode node1  = new HeroNode(1, "aa", "AA");
        HeroNode node2  = new HeroNode(1, "aa", "AA");
        HeroNode node3 = new HeroNode(1, "aa", "AA");
        //HeroNode node3 = new HeroNode(4, "dd", "DD");
        //HeroNode node1 = new HeroNode(2, "bb", "BB");
        //HeroNode node2 = new HeroNode(3, "cc", "CC");
        //创建单链表
        SingleLinkedList list = new SingleLinkedList();
        list.add(node);
        list.add(node2);
        list.add(node1);
        list.add(node3);
        list.list();
        list.removeElements(1);
        System.out.println("删除后");
        list.list();
        //list.addByNo(node);
        //list.addByNo(node2);
        //list.addByNo(node1);
        //list.addByNo(node3);
        //System.out.println("修改前");
        //list.list();

        //list.updateNodeByNo(new HeroNode(2, "FF", "ff"));

        //System.out.println("修改后");
        //list.deleteByNo(3);
        //打印链表
        //list.list();
        //System.out.println("链表的有效节点个数："+list.getValuedNode());
        //System.out.println(list.findLastIndexNode(3));
        //System.out.println("反转链表");
        //list.reverseList();
        //list.list();
        //System.out.println("逆序打印链表");
        //list.reversePrint();
        //System.out.println("合并两个有序链表");
        //SingleLinkedList list1 = new SingleLinkedList();
        //HeroNode node1 = new HeroNode(2, "bb", "BB");
        //HeroNode node2 = new HeroNode(3, "cc", "CC");
        //list1.add(node1);
        //list1.add(node2);

        //HeroNode heroNode = mergeTwoLists(node, node1);
        //list(heroNode);

    }

    /**
     * 合并两个有序链表
     * @param l1 第一个有序链表
     * @param l2 第二个有序链表
     * @return 合并后链表的头节点
     */
    public static HeroNode mergeTwoLists(HeroNode l1, HeroNode l2) {
        HeroNode prev = new HeroNode(0,"","");
        if(l1.next==null) return l2; //当l1链表为空时，直接返回l2
        if(l2.next==null) return l1; //当l2链表为空时，直接返回l1
        HeroNode cur = prev;
        while(l1!=null && l2!=null){
            if(l1.no<l2.no){
                cur.next = l1;
                l1 = l1.next; //l1向后遍历
            }else{
                cur.next = l2;
                l2 = l2.next; //l2向后遍历
            }
            cur = cur.next; //合并链表向后遍历
        }
        cur.next = l1==null?l2:l1; //将某个链表多余的部分单独添加
        return prev;
    }

    /**
     * 根据头节点head遍历打印链表
     * @param head 头节点
     */
    public static void list(HeroNode head){
        HeroNode temp = head;
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp);
        }
    }

}

//定义一个链表，管理各节点
class SingleLinkedList{
    //先初始化一个头节点，遍历需要
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到链表
    public void add(HeroNode headNode){
        HeroNode temp = head; //创建一个辅助节点
        while (temp.next != null) {
            //找到链表的最后
            temp = temp.next;//向后遍历
        }
        //退出循环后,temp就指向了最后一个节点，再进行add操作
        temp.next = headNode;
    }

    //根据排名添加节点到链表
    public void addByNo(HeroNode heroNode){
        //头节点遍历，遍历到no小于temp节点的后一个节点
        //进行插入，断掉前后节点的连接，将前节点的next指向插入节点，否则判断是否存在重复节点
        //插入节点的next指向后一个节点
        HeroNode temp = head;
        boolean flag = false; //判断是否存在相同节点
        while(true){
            //如果遍历到尾部直接退出循环
            if(temp.next == null){
                break;
            }
            //找到了插入的位置
            if(heroNode.no < temp.next.no){
                break;
            }else if(temp.next.no == heroNode.no){
                //说明添加的节点存在
                flag = true;
                break;
            }
            //没到尾部，没找到插入的位置，没有找到相同的节点，则继续向后遍历
            temp = temp.next;//向后遍历
        }
        if(flag){
            System.out.println(heroNode.no+"\t该节点已存在");
        }else{
            //如果没有出现相同的节点，则直接插入
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    public void removeElements(int val) {
        HeroNode cur = new HeroNode(0,"","");
        cur.next = head;
        HeroNode temp = cur; //用于遍历链表
        while(temp.next!=null){
            if(temp.next.no == val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next; // 向后遍历
            }
        }
    }

    //根据排名删除节点
    public void deleteByNo(int n){
        //遍历链表，对比no，如果找到
        //temp节点的next指向删除节点的下一个节点-- temp.next = temp.next.next;
        HeroNode temp = head;
        boolean flag = false;
        while(true){
            if(temp.next == null){
                //说明到达尾部
                break;
            }
            if(temp.next.no==n){
                //找到要删除的节点
                temp.next=temp.next.next; //进行删除操作
                flag = true;
                break;
            }
            temp = temp.next; //向后遍历
        }
        if(!flag) System.out.println("未找到要删除的节点序号:\t"+ n);
    }


    //根据no修改节点信息
    public void updateNodeByNo(HeroNode heroNode){
        if(isEmpty(head)){
            //判断是否为空链表
            System.out.println("链表为空");
            return;
        }
        //遍历链表找到需要修改的节点
        HeroNode temp = head;
        while(true){
            if(temp.next == null){
                //节点到达尾部
                System.out.println("未找到需要修改的节点");
                break;
            }
            //找到需要修改的节点
            if(temp.next.no == heroNode.no){
                //先删除当前节点，再插入修改后的节点
                deleteByNo(temp.next.no);
                addByNo(heroNode);
                //temp.next.name = heroNode.name;
                //temp.next.nickname = heroNode.nickname;
            }
            temp = temp.next;
        }
    }

    public boolean isEmpty(HeroNode head){
        return head.next == null;
    }

    /**
     * 打印链表
     */
    public void list(){
        HeroNode temp = head;
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * 获取单链表中有效节点个数
     */
    public int getValuedNode(){
        int count = 0;//节点个数
        HeroNode temp = head;
        if(temp.next==null){
            System.out.println("链表为空");
        }
        while(temp.next!=null){
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 查找单链表中的倒数第k个节点
     */
    public HeroNode findLastIndexNode(int index){
        if(head.next==null){
            return null;//链表为空
        }
        int length = getValuedNode()+1;//得到链表的长度
        if(index <=0 || index >=length ) return null; //对index作一个校验
        int num = 0;
        int count = length - index;//得到遍历到指定节点的个数
        HeroNode temp = head;
        //当遍历次数和count相同时则找到指定节点
        do {
            if (temp.next != null) {
                num++;//同事对遍历次数+1
                temp = temp.next; // 向后遍历
            }
        } while (num != count);
        return temp;
    }

    /**
     * 将单链表反转
     * 遍历链表的每个节点，每次将节点放在链表最前端
     * 将遍历到的节点的next指向新链表的最前端
     * 再将新链表的头节点指向遍历到的节点
     */
    public void reverseList(){
        HeroNode reverseNode = new HeroNode(0,"","");//new出一个新的头节点
        //当前链表为空，或只有一个节点则直接返回
        if(head.next == null || head.next.next==null) return;
        HeroNode cur = head.next; //定义辅助指针，遍历链表
        HeroNode next = null; //记录当前节点的下一个节点，在当前节点移动前，记录下一个节点的位置
        while(cur!=null){
            next = cur.next; // 记录当前节点的下一个节点，防止链表断掉
            cur.next = reverseNode.next;//将cur下一个节点指向新链表的最前端的有效节点
            reverseNode.next = cur; //让reverseNode指向当前节点
            cur = next; //将记录的节点赋给cur，进行下一次遍历
        }
        //将head.next 指向 reverseNode.next
        head.next = reverseNode.next;
        reverseNode.next=null;//让GC回收reverseNode节点
    }

    /**
     * 逆序打印链表
     */
    public void reversePrint(){
        if(head.next==null) return;
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        while(cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        while(stack.size()>0){
            System.out.println(stack.pop());
        }

    }

}

//定义一个HeroNode，每个HeroNode就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                ", next=" + next +
                '}';
    }
}
